package lc20240528;

import java.util.*;

/**
 *
 */
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class DeepCopyList {
    public static void main(String[] args) {
        //head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
        Node a = new Node(7);
        Node b = a.next = new Node(13);
        Node c = a.next.next = new Node(11);
        Node d = a.next.next.next = new Node(10);
        Node e = a.next.next.next.next = new Node(1);
        a.random = null;
        b.random = a;
        c.random = e;
        d.random = c;
        e.random = a;

        Node res=copyRandomList(a);

        while (res!=null){
            System.out.println(res.val);
            if (res.random!=null){
                System.out.println(res.random.val);

            }
            System.out.println("---------");
            res=res.next;
        }
    }

    public static Node copyRandomList(Node head) {
        Node p = head;
        Node q=head;
        Map<Node,Node> map=new HashMap<>();

        while (p!=null){
            Node newNode=new Node(p.val);
            map.put(p,newNode);
            p=p.next;
        }
        while (q!=null){
            Node res=map.get(q);
            if (q.next!=null){
                res.next=map.get(q.next);
            }
            if (q.random!=null){
                res.random=map.get(q.random);
            }
            q=q.next;
        }
        return map.get(head);
    }
}
